package bfs;

//TODO:2023/9/19   掌阅科技笔试题目

import realQuestion.jiezi.Test;

import java.util.LinkedList;
import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class ZhangYue {

//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        int m = scanner.nextInt();
//        char[][] input= new char[n][m];
//        for (int i = 0; i < n; i++) {
//            String next = scanner.next();
//        input[i]=    next.toCharArray();
//        }
//        Test1 test1 = new Test1();
//        int i = test1.find(n, m, input);
//        System.out.println(i);
//
//    }
//
//    public  int find(int n,int m,char[][] input){
//        int sx=-1;
//        int sy=-1;
//        int ex=-1;
//        int ey=-1;
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j <m; j++) {
//                if (input[i][j]=='s'){
//                    sx=i;
//                    sy=j;
//                }
//                if (input[i][j]=='e'){
//                    ex=i;
//                    ey=j;
//                }
//
//            }
//        }
//   find1(sx,sy,ex,ey,n,m);
//        return minLen;
//    }
//
//    int minLen=Integer.MAX_VALUE;
//    int len=0;
//    public  void find1(int sx,int  sy,int ex,int ey,int n,int m){
//        if (sx>n||sx<0||sy>n||sy<0){
//            return;
//        }
//        if (sx==ex&&sy==ey){
//            minLen=Math.min(minLen,len);
//            return;
//        }
//        for (int x = sx,y=sy; x <n &&y<m;) {
//    find1(sx-1,sy,ex,ey,n,m);
//    find1(sx,sy-1,ex,ey,n,m);
//    find1(sx+1,sy,ex,ey,n,m);
//    find1(sx,sy+1,ex,ey,n,m);
//        }
//
//    }
        public static void main(String[] args) {
            // 读取输入
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            char[][] maze = new char[n][m];
            for (int i = 0; i < n; i++) {
                String line = scanner.next();
                maze[i] = line.toCharArray();
            }
            scanner.close();

            // 调用最短路径算法
            int steps = shortestPath(maze, n, m);
            System.out.println(steps);
        }

        public static int shortestPath(char[][] maze, int n, int m) {
            int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向

            // 找到起点和终点的坐标
            int startX = 0, startY = 0, endX = 0, endY = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (maze[i][j] == 's') {
                        startX = i;
                        startY = j;
                    } else if (maze[i][j] == 'e') {
                        endX = i;
                        endY = j;
                    }
                }
            }

            // 广度优先搜索
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{startX, startY});
            boolean[][] visited = new boolean[n][m];
            visited[startX][startY] = true;
            int steps = 0;

            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int[] currPos = queue.poll();
                    int currX = currPos[0];
                    int currY = currPos[1];

                    // 到达终点
                    if (currX == endX && currY == endY) {
                        return steps;
                    }

                    // 向四个方向扩展
                    for (int[] direction : directions) {
                        int nextX = currX + direction[0];
                        int nextY = currY + direction[1];
                        // 判断下一个位置是否越界或者是障碍物
                        if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && maze[nextX][nextY] != '#' && !visited[nextX][nextY]) {
                            queue.offer(new int[]{nextX, nextY});
                            visited[nextX][nextY] = true;
                        }
                    }
                }
                steps++;
            }

            return -1; // 无法到达终点
        }
    }


